//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 
//
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
//一个节点也可以是它自己的祖先）。” 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
//输出：3
//解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
// 
//
// 示例 2： 
//
// 
//输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
//输出：5
//解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
// 
//
// 示例 3： 
//
// 
//输入：root = [1,2], p = 1, q = 2
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [2, 105] 内。 
// -109 <= Node.val <= 109 
// 所有 Node.val 互不相同 。 
// p != q 
// p 和 q 均存在于给定的二叉树中。 
// 
// Related Topics 树 深度优先搜索 二叉树 
// 👍 1373 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class LowestCommonAncestorOfABinaryTree {
    public static void main(String[] args) {
        Solution solution = new LowestCommonAncestorOfABinaryTree().new Solution();
    }public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 二叉树的最近公共祖先
     * 这个就比二叉搜索树复杂很多了，我的思路是判断当前非叶子结点是否为p或者q的父节点
     */
    TreeNode P,Q,res;
    Boolean flag = false;
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        P = p;
        Q = q;
        assistant(root);
        return res;
    }
    public void assistant(TreeNode root){
        if (root == null) return;
        assistant(root.left);
        assistant(root.right);
        if (!flag){
            if (root.left!=null){
                if (root.left.val == P.val) P = root;
                if (root.left.val == Q.val) Q = root;
            }
            if (root.right!=null){
                if (root.right.val == P.val) P = root;
                if (root.right.val == Q.val) Q = root;
            }
            if (P.val == Q.val){
                res = P;
                flag = true;
            }
        }
    }


    /**
     * 二刷：自顶向下搜的，比一刷更麻烦一些了，虽然比较直接，但是意义不大
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p.val,q.val);
        return res == null ? root : res;
    }
    public void dfs(TreeNode root, int p, int q){
        if (root == null) return;
        if (root.val == p){
            if ((root.left != null && find(root.left,q)) ||
                    (root.right != null && find(root.right,q))) res = root;
            return;
        }
        if (root.val == q){
            if ((root.left != null && find(root.left,p)) ||
                    (root.right != null && find(root.right,p))) res = root;
            return;
        }
        if (root.left != null && root.right !=null){
            if ((find(root.left,p)&&find(root.right,q))||(find(root.left,q)&&find(root.right,p))) res = root;
        }
        dfs(root.left,p,q);
        dfs(root.right,p,q);
    }

    public boolean find(TreeNode node, int val){
        if (node.val == val) return true;
        if (node.left != null && find(node.left, val)) return true;
        return node.right != null && find(node.right, val);
    }

    /**
     * 代码随想录题解：后序遍历，使用left和right接收返回值，并进行逻辑处理，遍历整棵树
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //找到目标节点直接返回
        if (root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);//左递归
        TreeNode right = lowestCommonAncestor(root.right, p, q);//右递归
        if (left != null && right != null) return root;//左右都不为空说明当前节点就是公共节点
        if (left == null && right == null) return null;//如果左右都为null就返回null
        return left == null ? right : left;//返回不是空的那个节点，这里包含了节点本身是祖先的情况
    }

    /**
     * 直接找两条路径出来进行迭代比较
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();
        dfs(root, p, path1);
        dfs(root, q, path2);
        for (int i = 0; i < Math.min(path1.size(), path2.size()); i++){
            if (i == Math.min(path1.size(), path2.size()) - 1) return path1.get(i);
            if (path1.get(i + 1) != path2.get(i + 1)) return path1.get(i);
        }
        return null;
    }

    public boolean dfs(TreeNode root, TreeNode target, List<TreeNode> path){
        if (root == null) return false;
        path.add(root);
        if (root == target) return true;
        if (dfs(root.left, target, path)) return true;
        if (dfs(root.right, target, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}











































